package org.example.myleet.p493;

/**
 * 本题是一道典型的分治算法题目，分治算法的步骤就是：分割+求解+合并。具体思考过程如下：
 *
 * 本题最小的子问题是什么？
 * 分割的子数组，长度为1，于是这个子问题的答案是0
 *
 * 如何理解跨越A1和A2的答案？
 * \forall i \in [0,len(A1)],j \in [0,len(A2)]∀i∈[0,len(A1)],j∈[0,len(A2)]，总有 A1[i] > 2*A2[j]A1[i]>2∗A2[j]
 *
 * 如何解决跨越A1和A2的问题？
 * 现在问题就变成了给出A1，A2两个数组，求A1中数值大于两倍的A2中数值的总个数。
 * 假如这时候A1，A2都是无序的，那我们还是要暴力遍历去解决。但如果他们都是有序的，我们就可以在线性时间内解决这个问题了。（我们也可以用二分查找来解决，但是时间复杂度就是线性对数的了。）
 *
 * 初始化两个指针i，j分别指向A1，A2的头部
 *
 * 如果A1[i] > 2*A2[j],那么A1[i]及A1[i]后面的所有元素都符合要求，更新答案并后移j
 *
 * 否则，后移i
 *
 * 接下来我们需要合并A1，A2以备解决后面更大的子问题使用
 *
 * 返回我们的答案
 *
 * 作者：yanghk
 * 链接：https://leetcode-cn.com/problems/reverse-pairs/solution/cjavapython3-gui-bing-pai-xu-by-yanghk/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * =========================
 *
 * 归并排序时：
 *
 * 保证了 i 小于 j（i属于左边数组，j属于右边数组）
 * 加上题目对翻转队的要求nums[i] > nums[j] * 2，即可计算出res
 */
class Solution {
    public int reversePairs(int[] nums) {
        // 使用归并排序，从小到大的进行排序
        if(nums.length < 2) {
            return 0;
        }
        return sort(nums,0,nums.length - 1);

    }

    public int sort(int[] nums,int left,int right) {
        if(left >= right) {
            return 0;
        }
        int mid = (left + right) / 2;
        int leftRes = sort(nums,left,mid);
        int rightRes = sort(nums,mid + 1,right);

        return leftRes + rightRes + merge(nums,left,mid,right);
    }

    public int merge(int[] nums,int left,int mid,int right) {
        int[] temp = new int[right - left + 1];
        int i = left;
        int j = mid + 1;
        int res = 0;
        int flag = 0;
        // 计算翻转对
        while(i <= mid && j <= right) {
            if(nums[i] > 2 * (long)nums[j]) {
                res += mid - i + 1;
                j++;
            }else {
                i++;
            }
        }

        i = left;
        j = mid + 1;

        // 进行排序
        while(i <= mid && j <= right) {

            if(nums[i] < nums[j]) {
                temp[flag++] = nums[i++];
            }else {
                temp[flag++] = nums[j++];
            }
        }

        while(i <= mid) {
            temp[flag++] = nums[i++];
        }
        while(j <= right) {
            temp[flag++] = nums[j++];
        }
        for(int k = 0;k < temp.length;k++) {
            nums[left + k] = temp[k];
        }
        return res;
    }
}
